1. Field of the Invention
The present invention may relate to digital computer systems and more particularly to data base systems implemented in digital computer systems and to systems and methods for optimizing queries in data base systems.
2. Description of Prior Art
Data base systems are computer-based record keeping systems which allow users to perform operations such as locating, adding, deleting, and updating records stored in a computer system. The operation of locating data in a data base is called a query. Since data bases may contain large numbers of records and a given query may require combination of information from different records, a recurrent problem in the design of data base systems has been making queries more efficient. Most prior-art data base systems have included components termed query optimizers, which take a given query and transform it into an optimized query which is equivalent to the given query, but which may be executed more efficiently than the given query. Either the optimizer or another component called the code generator then transforms the optimized query into query code which is executable by the data base system to produce the records requested in the query.
The design of query optimizers and code generators is complex, and is made more so by the fact that optimization may occur at several levels. First, the query being optimized may be logically transformed into an equivalent but more efficient form. Second, the optimized query may be able to take advantage of information such as indexes which the data base system maintains about the records it keeps. Third, the optimized query may be able to take advantage of various methods for accessing the information sought. Thus, efficient prior-art optimizers have tended to be strongly dependent on the specific implementation of the data base system and on the specific digital data processing system in which they were employed. The effects of these dependencies have been threefold:
(1) The need for an extensive understanding of the data base system and the digital data processing system has made optimizers difficult to design and has increased the amount of time needed to create them. PA1 (2) Optimizers have been difficult to maintain, both because they are complicated, and because those who maintain them need the same extensive understanding of the data base system and the digital data processing system as those who create them. PA1 (3) Because of the dependencies of the optimizer on the implementation of the data base system and the digital data processing system, any change in either has required extensive modification of the optimizer. For this reason, it has also been difficult to adapt optimizers to different systems.
Code generators have the same dependencies as optimizers, and have been similarly difficult to design, maintain, and adapt. These problems of prior-art optimizers and code generators, and others as well, have been solved by the optimizer and code generator of the present invention.